package com.cn.algorithm01;

/**
 * @author hels
 * @version 1.0
 * @date 2021/10/12 15:04
 * 无序且相邻数字不相等数组，寻找一个局部最小数据，
 */
public class Code05_PartMin {

    //生成随机数组，且相邻不相等
    public static int[] createArray(int size, int value) {
        int len = (int) (Math.random() * (size + 1));
        int[] arr = new int[len];
        //此时可能创建空数组
        if (arr.length > 0){
            arr[0] = (int)(Math.random() * (value + 1));
            for (int i = 1; i < len; i++) {
                do {
                    arr[i] = (int)(Math.random() * (value + 1));
                } while (arr[i] == arr[i - 1]);
            }
        }

        return arr;
    }

    //数组和随机数输出
    public static void printArray(int[] arr) {
        for (int n : arr) {
            System.out.print(n + " ");
        }
    }

    public static void main(String[] args) {
        int maxSize = 10, maxValue = 20;
        int times = 10000;
        boolean ans = true;

        System.out.println("开始测试");
        for (int i = 0; i < times; i++) {
            int[] arr = createArray(maxSize, maxValue);
            int minIndex = oneMinIndex(arr);
            try {
                if (!checkMin(arr, minIndex)) {
                    ans = false;
                }
            } catch (Exception e) {
                printArray(arr);
                System.out.println("最小位置：" + minIndex);
                ans = false;
            }
        }
        System.out.println(ans ? "nice" : "出错了");

    }

    // 核心算法，找到局部最小下标
    public static int oneMinIndex(int[] arr) {
        int minIndex = -1;
        if (arr == null || arr.length ==0) {
            return minIndex;
        }

        int N = arr.length;
        if (N == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[N-2] > arr[N - 1]) {
            return N-1;
        }

        int left = 0, right = N-1;
        while (left < right-1) {

            int mid = (left + right) / 2;

            if (arr[mid-1] > arr[mid] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid - 1] < arr[mid]) {
                    right = mid - 1;
                } else if (arr[mid] > arr[mid + 1]) {
                    left = mid + 1;
                }
            }

        }
        //当所有条件都不满足时，返回-1
        return arr[left] < arr[right] ? left : right;
    }

    // 对最小下标进行校验
    public static boolean checkMin(int[] arr, int minIndex) {
        if (arr == null || arr.length == 0) {
            return minIndex == -1;
        }

        int left = minIndex - 1;
        int right = minIndex + 1;
        boolean leftBigger = left >= 0 ? (arr[left] > arr[minIndex]) : true;
        boolean rightBigger =  right < arr.length ? (arr[minIndex] < arr[right]) : true;
        return leftBigger && rightBigger;
    }

}
